package com.lw.leetcode.greedy.b;

import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * LCP 30. 魔塔游戏
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/13 13:35
 */
public class MagicTower {


    public static void main(String[] args) {
        MagicTower test = new MagicTower();

        // 1
        int[] arr = {100, -234, 100, 100, -250, 43, 57, -234, 575, 34, -435, 7, -60, -140, -50, -50, 100, 1500};

        // 1
//        int[] arr = {100, 100, 100, -250, -60, -140, -50, -50, 100, 150};

        // -1
//        int[] arr = {-200, -300, 400, 0};

        // -1
//        int[] arr = {-1,-1,10};

//        int i = test.magicTower(arr);
//        System.out.println(i);
    }

    public int magicTower(int[] nums) {
        long sum = 1L;
        for (int num : nums) {
            sum += num;
        }
        if (sum < 0) {
            return -1;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        sum = 1L;
        int count = 0;
        for (int num : nums) {
            sum += num;
            if (num < 0) {
                queue.add(num);
                if (sum <= 0) {
                    sum -= queue.poll();
                    count++;
                }
            }
        }
        return count;
    }

}
